package listbyorder.access101_200.test113;

import listbyorder.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 11:31
 */
public class Solution1 {

    // dfs回溯
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        dfs(res, root, sum, 0, new ArrayList<Integer>());
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode root, int sum, int cur, ArrayList<Integer> path) {
        if (root == null) {
            if(cur == sum){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        ArrayList<Integer> before = new ArrayList<>(path);
        if (root.left == null) {
            path.add(root.val);
            dfs(res, root.right, sum, cur + root.val, path);
        } else if (root.right == null) {
            path.add(root.val);
            dfs(res, root.left, sum, cur + root.val, path);
        } else {
            // 首先考虑左边的情况
            path.add(root.val);
            dfs(res, root.left, sum, cur + root.val, path);

            // 然后再考虑后边的情况
            before.add(root.val);
            dfs(res, root.right, sum, cur + root.val, before);
        }
    }
}
